package main;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

import main.api.GPSProblem;
import main.api.GPSRule;
import main.api.GPSState;
import main.exception.NotAppliableException;

public class GPSEngine {

	static private List<GPSNode> open = new LinkedList<GPSNode>();

	static private List<GPSNode> closed = new ArrayList<GPSNode>();

	static private GPSProblem problem;

	static private SearchStrategy strategy;
	
	static private int desiredLevel = 0;

	public static void engine(GPSProblem myProblem, SearchStrategy myStrategy) {

		long initTime = System.currentTimeMillis();
		long endTime;
		problem = myProblem;
		strategy = myStrategy;

		GPSNode rootNode = new GPSNode(problem.getInitState(), 0);
		boolean finished = false;
		boolean failed = false;
		long explosionCounter = 0;
		open.add(rootNode);
		System.out.println(rootNode.getState());
		while (!failed && !finished) {
			if (open.size() <= 0) {
				failed = true;
				System.out.println("Expanded nodes: " + explosionCounter);
			} else {
				GPSNode currentNode = open.get(0);
				closed.add(currentNode);
				open.remove(0);
				if (isGoal(currentNode)) {
					endTime = System.currentTimeMillis();
					finished = true;
					int cantNiveles = 0;
					GPSNode n = new GPSNode(currentNode.getState(), currentNode.getCost());;
					n.setParent(currentNode.getParent());
					
					while(n.getParent() != null){
						cantNiveles++;
						n = n.getParent();
					}
					
					System.out.println(currentNode.getSolution());

					System.out.println("Tiempo de ejecucion (s): " + ((endTime-initTime)/1000.0));
					System.out.println("Cantidad de pasos: "+cantNiveles);
					System.out.println("Expanded nodes: " + explosionCounter);
					System.out.println("Nodos frontera: " + open.size());
					System.out.println("Estados generados: " + (explosionCounter+open.size()));
				} else {
					explosionCounter++;
					explode(currentNode);
				}
			}
		}

		if (finished) {
			System.out.println("OK! solution found!");
		} else if (failed) {
			System.err.println("FAILED! solution not found!");
		}
	}

	private static boolean isGoal(GPSNode currentNode) {
		return currentNode.getState() != null
				&& currentNode.getState().compare(problem.getGoalState());
	}

	private static boolean explode(GPSNode node) {
		if(problem.getRules() == null){
			System.err.println("No rules!");
			return false;
		}
		
		for (GPSRule rule : problem.getRules()) {
			GPSState newState = null;
			try {
				newState = rule.evalRule(node.getState());
			} catch (NotAppliableException e) {
				//Do nothing
			}
			
			if (newState != null
					&& !checkBranch(node, newState)
					&& !checkOpenAndClosed(node.getCost() + rule.getCost(),
							newState)) {
				GPSNode newNode = new GPSNode(newState, node.getCost()
						+ rule.getCost());
				newNode.setParent(node);
				addNode(newNode);
			}
		}
		return true;
	}

	private static void addNode(GPSNode node) {
		switch (strategy) {
		case BFS:
			open.add(node);
			break;
		case DFS:
			((LinkedList<GPSNode>) open).addFirst(node);
			break;
		case ProfIter:
			int level = 0;
			GPSNode n = new GPSNode(node.getState(), node.getCost());
			n.setParent(node.getParent());
			
			while(n.getParent() != null){
				level++;
				n = n.getParent();
			}
			if (level < desiredLevel) {
				open.add(node);
			}else{
				open.clear();
				closed.clear();
				open.add(new GPSNode(problem.getInitState(), 0));
				desiredLevel++;
			}
			break;
		case Greedy:
			int nodeCost = problem.getHValue(node.getState());
			int i=0;
			while(i < open.size() && nodeCost >= problem.getHValue(open.get(i).getState())){
				i++;
			}
			open.add(i, node);
			break;
		case AStar:
			int index = Collections.binarySearch(open, node,
					new Comparator<GPSNode>() {

						@Override
						public int compare(GPSNode o1, GPSNode o2) {
							Integer f1 = o1.getCost()
									+ problem.getHValue(o1.getState());
							Integer f2 = o2.getCost()
									+ problem.getHValue(o2.getState());
							if (f1 < f2) {
								return -1;
							} else if (f1 == f2) {
								return 0;
							} else {
								return 1;
							}
						}
					});
			if (index >= 0) {
				((LinkedList<GPSNode>) open).add(index, node);
			} else {
				((LinkedList<GPSNode>) open).add(-1 * (index + 1), node);
			}
			break;
		default:
			open.add(node);
			break;
		}
	}

	
	private static boolean checkOpenAndClosed(Integer cost, GPSState state) {
		/*Si tengo algun camino ya cargado (que todav�a no recorr�) igual al que acabo de generar pero con menor costo, devuelvo true*/
		for (GPSNode openNode : open) {
			if (openNode.getState().compare(state) && openNode.getCost() <= cost) {
				return true;
			}
		}
		
		/*Si tengo algun camino ya cargado (que ya recorr�) igual al que acabo de generar pero con menor costo, devuelvo true*/
		for (GPSNode closedNode : closed) {
			if (closedNode.getState().compare(state)
					&& closedNode.getCost() <= cost) {
				return true;
			}
		}
		return false;
	}

	private static boolean checkBranch(GPSNode parent, GPSState state) {
		if (parent == null) {
			return false;
		}
		
		return checkBranch(parent.getParent(), state)
				|| state.compare(parent.getState());
	}

}
